package com.sxt;
/**双向链表*/
public class MyDoubleLinkedList01<E> implements MyList<E>{
    /*用内部类来定义双向节点对象的类*/
    class Node01<E> {
        private Node01<E> prev01;
        E item01;
        private Node01<E> next01;

         Node01(Node01<E> prev01, E item01, Node01<E> next01) {
            this.prev01 = prev01;
            this.item01 = item01;
            this.next01 = next01;
        }
    }
    private int size;//记录元素个数
    private Node01 tail;//记录尾节点
    private Node01 head;//记录头节点
    //添加元素
    @Override
    public void add(E element) {
        this.linkedLast(element);

    }
    /*将节点对象添加到双向链表尾部*/
    private void linkedLast(E element){
        //获取尾节点
        Node01 t = tail;
        //创建新的节点
        Node01<E> node01 = new Node01<>(t,element,null);
        //将新节点为尾节点
        this.tail = node01;

        if(t == null){
            this.head=node01;
        }else {
            t.next01 = node01;
        }
        this.size++;
    }


    //获取元素
    @Override
    public E get(int index) {
        this.checkIndex(index);
        //创建获得元素的对象
        Node01<E> node01 = this.getNode(index);
        return node01.item01;
    }
    //检验index合法性
    private void checkIndex(int index){
        if(!(index>=0 && index<this.size)){
            throw new IndexOutOfBoundsException("Index"+index+"Size"+size);
        }
    }
    //根据位置获取指定节点对象
    private Node01 getNode(int index){
        //个数除以2  判断当前位置距离头或尾哪个节点更近
        if(index<(this.size >> 1)){
            Node01 node01 = this.head;
            //索引从0开始
            for(int i=0;i<index;i++){
                node01=node01.next01;
            }
            return node01;
        }else {
            Node01 node01 = this.tail;
            for(int i=this.size-1;i>index;i--){
                node01 = node01.prev01;
            }
            return node01;
        }
    }
    //元素个数
    @Override
    public int size() {

        return this.size;
    }
    //删除元素
    @Override
    public E remove(int index) {
        //校验index合法性
        this.checkIndex(index);
        //根据指定位置获取节点对象
        Node01<E> node01 = this.getNode(index);
        //获取节点对象中的元素
        E item = node01.item01;
        ////判断当前节点是否为空
        //判断是否为头节点
        if(node01.prev01 == null ){
            this.head=node01;
        }else{
            /*当前节点的前一个节点挂接当前节点的下一个节点*/
            node01.prev01.next01 = node01.next01;
        }
        if(node01.next01 == null){
            this.tail = node01;
        }else {
            /*当前节点的后一个节点挂接当前节点的前一个节点*/
            node01.next01.prev01 = node01.prev01;
        }
        //当前接点断掉与它直接前驱节点的连接
        node01.prev01 = null;
        node01.next01 = null;
        node01.item01 = null;
        this.size--;
        return item;
    }
    /*在双向链表的头添加元素*/
    public void addFirst(E element){
        this.linkFirst(element);
    }
    /*在双向链表的头添加元素*/
    private void linkFirst(E element){
        //获取头对象
        Node01 head = this.head;
        //创建对象  node.next指向下一个节点head,所以第三个参数填head,
        // 是前接点向后节点挂接
        Node01 node01 = new Node01(null,element,head);
        //将新节点定义为头节点
         this.head = node01;
        //判断当前链表中是否有节点，如果没有那么该节点即是头节点也是尾节点
        if(head == null){
            this.tail = node01;
        }else {
            head.prev01 = node01;
        }
        this.size++;
    }
    public void addLast(E element){
        this.linkedLast(element);
    }
    public static void main(String[] args) {
      /*  MyList<String> myList = new MyDoubleLinkedList01<>();
        myList.add("a");
        myList.add("s");
        myList.add("x");
        myList.add("c");
        System.out.println(myList.size());
        System.out.println(myList.remove(1));
        for (int i =0;i< myList.size();i++){
            System.out.println(myList.get(i));
        }*/
        /*因为上面的对象引用是接口类型定义，接口里没有addFirst与addLast方法
         * 所以下面的定义要用本身定义*/
        MyDoubleLinkedList01<String> mydl = new MyDoubleLinkedList01<>();
        mydl.add("a");
        mydl.addFirst("S");
        mydl.addLast("c");
        mydl.add("e");
        System.out.println(mydl.size);
        for(int i=0;i<mydl.size;i++){
            System.out.println(mydl.get(i));
        }

    }
}
